#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int px[1<<20],py[1<<20];
vector<int> inidx[20];
const int LMT = 2e6;
bool cmp1(int x,int y){
    return px[x] < px[y];
}
bool cmp2(int x,int y){
    return py[x] < py[y];
}
struct K_D{
    struct zone{
        int x1,x2,y1,y2;
    } zs[1<<19];
    int p1[1<<19],p2[1<<19],p3[1<<19],p4[1<<19];
    inline int dis(int p,int x,int y){
        return abs(px[p] - x) + abs(py[p] - y);
    }
    int ls[1<<19],rs[1<<19];
    int build(vector<int> &p,int l,int r){
        if(r < l){
            return 0;
        } 
        if(l == r){
            p1[p[l]] = p2[p[l]] = p3[p[l]] = p4[p[l]] = p[l];
            zs[p[l]] = {px[p[l]],px[p[l]],py[p[l]],py[p[l]]};
            return p[l];
        }
        long long sx = 0;
        long long sx1 = 0;
        long long sy = 0;
        long long sy1 = 0;
        zone nw = {LMT,-LMT,LMT,-LMT};
        for(int i = l;i <= r;i++){
            sx += px[p[i]];
            sx1 += 1ll*px[p[i]]*px[p[i]];
            sy += py[p[i]];
            sy1 += 1ll*py[p[i]]*py[p[i]];
            nw.x1 = min(nw.x1,px[p[i]]);
            nw.x2 = max(nw.x2,px[p[i]]);
            nw.y1 = min(nw.y1,py[p[i]]);
            nw.y2 = max(nw.y2,py[p[i]]);
        }
        int len = r - l + 1;
        double xw = 1.0*sx1/len - (1.0*sx/len)*(1.0*sx/len),yw = 1.0*sy1/len - (1.0*sy/len)*(1.0*sy/len); 
        int now;
        int mid = (l + r)/2;
        if(xw > yw){
            nth_element(p.begin() + l,p.begin() + mid,p.begin() + r + 1,cmp1);
            now = p[mid];
        }else{
            nth_element(p.begin() + l,p.begin() + mid,p.begin() + r + 1,cmp2);
            now = p[mid];
        }
        zs[now] = nw;
        ls[now] = build(p,l,mid - 1);
        rs[now] = build(p,mid + 1,r);
        p1[now] = p2[now] = p3[now] = p4[now] = now;
        if(ls[now] && dis(p1[ls[now]],nw.x1,nw.y1) < dis(p1[now],nw.x1,nw.y1)){
            p1[now] = p1[ls[now]];
        }
        if(rs[now] && dis(p1[rs[now]],nw.x1,nw.y1) < dis(p1[now],nw.x1,nw.y1)){
            p1[now] = p1[rs[now]];
        }

        if(ls[now] && dis(p2[ls[now]],nw.x2,nw.y1) < dis(p2[now],nw.x2,nw.y1)){
            p2[now] = p2[ls[now]];
        }
        if(rs[now] && dis(p2[rs[now]],nw.x2,nw.y1) < dis(p2[now],nw.x2,nw.y1)){
            p2[now] = p2[rs[now]];
        }

        if(ls[now] && dis(p3[ls[now]],nw.x2,nw.y2) < dis(p3[now],nw.x2,nw.y2)){
            p3[now] = p3[ls[now]];
        }
        if(rs[now] && dis(p3[rs[now]],nw.x2,nw.y2) < dis(p3[now],nw.x2,nw.y2)){
            p3[now] = p3[rs[now]];
        }

        if(ls[now] && dis(p4[ls[now]],nw.x1,nw.y2) < dis(p4[now],nw.x1,nw.y2)){
            p4[now] = p4[ls[now]];
        }
        if(rs[now] && dis(p4[rs[now]],nw.x1,nw.y2) < dis(p4[now],nw.x1,nw.y2)){
            p4[now] = p4[rs[now]];
        }
        return now;
    }
    inline int dis(int x1,int y1,int x2,int y2){
        return abs(x1 - x2) + abs(y1 - y2);
    }
    inline int min_dis(int now,int x,int y){
        if(zs[now].x1 <= x && x <= zs[now].x2 && zs[now].y1 <= y && y <= zs[now].y2){
            return 0;
        }
        if(zs[now].x1 <= x && x <= zs[now].x2){
            return min(abs(y - zs[now].y1),abs(y - zs[now].y2));
        }
        if(zs[now].y1 <= y && y <= zs[now].y2){
            return min(abs(x - zs[now].x1),abs(x - zs[now].x2));
        }
        return min(min(dis(zs[now].x1,zs[now].y1,x,y),dis(zs[now].x1,zs[now].y2,x,y)),min(dis(zs[now].x2,zs[now].y1,x,y),dis(zs[now].x2,zs[now].y2,x,y)));
    }
    int q1(int now,int x,int y){
        if(x <= zs[now].x1 && y <= zs[now].y1){
            return dis(px[p1[now]],py[p1[now]],x,y);
        }
        int res = 0x3f3f3f3f;
        if(px[now] >= x && py[now] >= y){
            res = dis(px[now],py[now],x,y);
        }
        if(ls[now] && zs[ls[now]].x2 >= x && zs[ls[now]].y2 >= y && min_dis(ls[now],x,y) < res){
            res = min(res,q1(ls[now],x,y));
        }
        if(rs[now] && zs[rs[now]].x2 >= x && zs[rs[now]].y2 >= y && min_dis(rs[now],x,y) < res){
            res = min(res,q1(rs[now],x,y));
        }
        return res;
    }
    int q2(int now,int x,int y){
        if(x >= zs[now].x2 && zs[now].y1 >= y){
            return dis(px[p2[now]],py[p2[now]],x,y);
        }
        int res = 0x3f3f3f3f;
        if(px[now] <= x && py[now] >= y){
            res = min(res,dis(px[now],py[now],x,y));
        }
        if(ls[now] && zs[ls[now]].x1 <= x && zs[ls[now]].y2 >= y && min_dis(ls[now],x,y) < res){
            res = min(res,q2(ls[now],x,y));
        }
        if(rs[now] && zs[rs[now]].x1 <= x && zs[rs[now]].y2 >= y && min_dis(rs[now],x,y) < res){
            res = min(res,q2(rs[now],x,y));
        }
        return res;
    }

    int q3(int now,int x,int y){
        if(x >= zs[now].x2 && zs[now].y2 <= y){
            return dis(px[p3[now]],py[p3[now]],x,y);
        }
        int res = 0x3f3f3f3f;
        if(px[now] <= x && py[now] <= y){
            res = dis(px[now],py[now],x,y);
        }
        if(ls[now] && zs[ls[now]].x1 <= x && zs[ls[now]].y1 <= y && min_dis(ls[now],x,y) < res){
            res = min(res,q3(ls[now],x,y));
        }
        if(rs[now] && zs[rs[now]].x1 <= x && zs[rs[now]].y1 <= y && min_dis(rs[now],x,y) < res){
            res = min(res,q3(rs[now],x,y));
        }
        return res;
    }

    int q4(int now,int x,int y){
        if(x <= zs[now].x1 && zs[now].y2 <= y){
            return dis(px[p4[now]],py[p4[now]],x,y);
        }
        int res = 0x3f3f3f3f;
        if(px[now] >= x && py[now] <= y){
            res = dis(px[now],py[now],x,y);
        }
        if(ls[now] && zs[ls[now]].x2 >= x && zs[ls[now]].y1 <= y && min_dis(ls[now],x,y) < res){
            res = min(q4(ls[now],x,y),res);
        }
        if(rs[now] && zs[rs[now]].x2 >= x && zs[rs[now]].y1 <= y && min_dis(rs[now],x,y) < res){
            res = min(q4(rs[now],x,y),res);
        }
        return res;
    }
    void remove(int now){
        if(!now){
            return;
        }
        if(ls[now]){
            remove(ls[now]);
        }
        if(rs[now]){
            remove(rs[now]);
        }
        ls[now] = rs[now] = 0;
    }
}kdt;
int rot[18];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i = 0;i < 19;i++){
        for(int j = 1<<i;j < (1<<(i + 1));j++){
            inidx[i].push_back(j);
        }
    }
    while(n){
        int lb = n&(-n);
        int ct = 31 -  __builtin_clz(lb);
        for(int j = 1<<ct;j < (1<<(ct + 1));j++){
            cin>>px[j]>>py[j];
        }
        rot[ct] = kdt.build(inidx[ct],0,inidx[ct].size() - 1);
        n -= lb;
    }
    for(int i = 1;i<=m;i++){
        int op;
        cin>>op;
        if(op == 1){
            int x,y;
            cin>>x>>y;
            if(!rot[0]){
                px[1] = x;
                py[1] = y;
                rot[0] = kdt.build(inidx[0],0,0);
            }else{
                px[0] = x;
                py[0] = y;
                int p = 0;
                for(;rot[p];p++){
                    kdt.remove(rot[p]);
                    rot[p] = 0;
                }
                memcpy(px + (1<<p),px,sizeof(int)*(1<<p));
                memcpy(py + (1<<p),py,sizeof(int)*(1<<p));
                memset(px,0,sizeof(int)*(1<<p));
                memset(py,0,sizeof(int)*(1<<p));
                rot[p] = kdt.build(inidx[p],0,inidx[p].size() - 1);
            }
        }else{
            int x,y;
            cin>>x>>y;
            int ans = 0x3f3f3f3f;
            for(int i = 0;i < 18;i++){
                if(!rot[i])continue;
                if(kdt.zs[rot[i]].x2 >= x && kdt.zs[rot[i]].y2 >=y){
                    ans = min(ans,kdt.q1(rot[i],x,y));
                }
                if(kdt.zs[rot[i]].x1 <= x && kdt.zs[rot[i]].y2 >= y){
                    ans = min(ans,kdt.q2(rot[i],x,y));
                }
                if(kdt.zs[rot[i]].x1 <= x && kdt.zs[rot[i]].y1 <= y){
                    ans = min(ans,kdt.q3(rot[i],x,y));
                }
                if(kdt.zs[rot[i]].x2 >= x && kdt.zs[rot[i]].y1 <= y){
                    ans = min(kdt.q4(rot[i],x,y),ans);
                }
            }
            cout<<ans<<'\n';
        }
    }
}